//300 最长的递增子序列
/*
给定一个未排序的整数数组，求最长的递增子序列

输入输出样例
	输入是一个一维数组，输出是一个正整数，表示最长递增子序列的长度

Input: [10,9,2,5,3,7,101,18]
Output: 4
在这个样例中，最长递增子序列之一是 [2,3,7,18]
*/
int lengthOfLIS(vector<int> &nums)
{
	int n = nums.size();
	if (n <= 1)
		return n;
	vector<int> dp;
	dp.push_back(nums[0]);
	for (int i = 1; i < n; ++i)
	{
		if (dp.back() < nums[i])
		{
			dp.push_back(nums[i]);
		}
		else
		{
			auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);
			*itr = nums[i];
		}
	}
	return dp.size();
}
